home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-01
/
bfsorts.zip
/
HSORT.C
< prev
next >
Wrap
C/C++ Source or Header
|
1991-03-31
|
6KB
|
224 lines
/***********************************************************************/
/* SORT(): Non-Recursive Heap Sort function. */
/* See the function declaration for calling information. */
/* Function is by Bruce Feist; please contact me on CompuServe with */
/* a message on BPROGB, MACDEV, or EASYPLEX if you have any */
/* questions or problems. */
/* You can also reach me at the Enlightened Board, at (703) 370-9528, */
/* N/8/1 */
/* Feel free to make use of this code in your own programs. */
/***********************************************************************/
#define VERBOSE (0)
#include <process.h>
#include <alloc.h>
#include <stdlib.h>
#include <mem.h>
#include <stddef.h>
#include <stdio.h>
#include "sort.h"
static void build_heap (void), extract_heap (void);
static void heapify (int, int);
static void show_node (int);
#if VERBOSE
static void show_heap (void);
#endif
/* heapsort uses an array of pointers as its data structure to */
/* represent the heap. */
/* Children of slot i are slots 2i+1 and 2i+2. */
/* Note: as an alternative, we could have made the input array */
/* into a heap (instead of messing with the pointers. */
static char *base, *temp_record;
static int nelem, width, (*compare)(void *, void *);
int
hsort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
{
base = pbase;
nelem = pnelem;
width = pwidth;
compare = pcompare;
if ((temp_record = malloc (pwidth)) == NULL)
return S_NOMEM;
#if VERBOSE
printf ("Sort (base = %p, n = %u, w = %u)\n", base, nelem, width);
#endif
build_heap ();
extract_heap ();
free (temp_record);
return S_OK;
} /* end hsort */
void
build_heap()
{
register int left;
register char *left_ptr;
int right;
#if VERBOSE
puts ("Building heap. . .\n");
#endif
right = nelem - 1;
for (left = (nelem >> 1) - 1, left_ptr = base + width * left;
1; /* keep going until the 'break' */
left--, left_ptr -= width)
{
#if VERBOSE
printf ("temp <- %d to start heapification.\n", left);
#endif
memcpy (temp_record, left_ptr, width);
heapify (left, right);
if (! left)
break;
}
} /* end build_heap */
void
extract_heap ()
{
register int right;
register char *right_ptr;
#if VERBOSE
puts ("Extracting from heap. . .\n");
#endif
for (right = nelem - 1, right_ptr = base + width * right;
1; /* continue until the 'break' */
right_ptr -= width)
{
memcpy (temp_record, right_ptr, width);
memcpy (right_ptr, base, width);
#if VERBOSE
printf ("temp <- %d to start extract\n", right);
printf ("%d <- %d to start extract\n", right, 0);
printf ("Returning %lf\n", ((double *) base) [right]);
#endif
if (! --right)
break;
heapify (0, right);
}
#if VERBOSE
printf ("%d <- temp to finish extract\n", 0);
#endif
memcpy (base, temp_record, width);
} /* end extract_heap */
/* When heapify is called, (left+1,right) is already heapified and */
/* temp_record contains what we'd like to add to it to make (left,right) */
/* a heap. */
/* So, we look for the first descendent of 'left' that's bigger than */
/* it. All of its ancestors move up a generation, and temp_record */
/* becomes its parent. */
void
heapify (int left, int right)
{
register int child;
register char *ptr_child;
char *ptr_child2, *ptr_parent;
child = left;
ptr_child = base + child * width;
#if VERBOSE
show_heap();
printf ("Heapifying from %d to %d.\n", left, right);
#endif
while (1) /* continue until the 'break' */
{
child <<= 1;
child++;
ptr_parent = ptr_child;
if (child > right) /* if parent was a leaf, replace with temp_record */
{
#if VERBOSE
printf ("%d <- temp since %d is leaf.\n", parent, parent);
#endif
memcpy (ptr_parent, temp_record, width);
break;
} /* end if */
ptr_child = base + child * width;
if (child < right) /* Is there more than one child? */
{
/* Use the biggest child. */
if (compare (ptr_child, ptr_child2 = ptr_child + width) < 0)
{
child++;
ptr_child = ptr_child2;
} /* end if ptr_child < ptr_child2 */
} /* end if child < right */
if (compare (temp_record, ptr_child) >= 0) /* Is temp_record bigger? */
{
#if VERBOSE
printf ("%d <- temp since temp is bigger than %d.\n", parent, child1);
#endif
memcpy (ptr_parent, temp_record, width);
break;
}
#if VERBOSE
printf ("%d <- %d since we're not done yet\n", parent, child1);
#endif
memcpy (ptr_parent, ptr_child, width); /* Promote by a generation */
} /* end while TRUE */
#if VERBOSE
puts ("Done heapifying.");
show_heap();
#endif
} /* end heapify */
void
show_heap ()
{
puts ("The heap:");
show_node (0);
}
void
show_node (int node_id)
{
int child1, child2, ancestor;
child1 = node_id * 2 + 1;
child2 = child1 + 1;
printf ("%.4lf\t", ((double *) base) [node_id]);
if (child1 < nelem)
show_node (child1);
else
putchar ('\n');
if (child2 < nelem)
{
for (ancestor = 1; ancestor < child2; ancestor <<= 1)
putchar ('\t');
show_node (child2);
}
} /* end show_node */